suffix array

prefix…接頭辞

suffix…接尾辞

i文字目〜最後の文字、みたいなのを並べたのをソートした配列を使う。

ソートされてるならにぶたんが使えるから、m文字の単語を検索するなら、O(m*logn)に抑えられる。

普通にSuffix Array(SA)を作ろうとするとO(n*nlogn)かかるけど、SA-ISを使うとO(n)で構築できる。いいね、知らんけど。